package org.example.myleet.p446;

import java.util.HashMap;
import java.util.Map;

/**
 * 官方解，动态规划
 */
public class Solution {
    public int numberOfArithmeticSlices(int[] nums) {
        int count = 0;
        //动态规划
        Map<Long, Integer>[] diffCntMapArr = new Map[nums.length];
        Map<Long, Integer> emptyMap = new HashMap<>();
        diffCntMapArr[0] = emptyMap;
        for (int i = 1; i < nums.length; ++i) {
            Map<Long, Integer> diffCntMap = new HashMap<>();
            for (int j = i - 1; j >= 0; --j) {
                //遍历i位置前面的所有元素，计算公差
                long diff = (long) nums[i] - (long) nums[j];
                //按照公差找出对应的弱等差数列数量
                Integer prevCnt = diffCntMapArr[j].getOrDefault(diff, 0);
                //累加到结果中
                count += prevCnt;
                //计算当前位置对应公差的的弱等差数列数量，其结果等于nums[j]的等差数列数量累加到当前结果中
                //并且由于nums[i]、nums[j]这一对也是弱等差数列，因此再+1
                Integer curCnt = diffCntMap.getOrDefault(diff, 0);
                curCnt += prevCnt + 1;
                diffCntMap.put(diff, curCnt);
            }
            diffCntMapArr[i] = diffCntMap;
        }
        return count;
    }
}
